<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>对象数组去重</title>
</head>
<body>
<h2>对象数组去重性能测试</h2>
<p>测试数据是800万个id值为0~999之间随机数的对象</p>
<p>去重后长度应为1000(留下0~999的id)</p>
<hr>
<script>
    //测试数据
    const objs=[];
    for (let i = 0; i < 8_000_000; i++) {
        objs.push({id:Math.floor(Math.random()*1_000)});
    }

    const prop='id';

    function showPrint(method,time,len) {
        const p=document.createElement('p');
        p.textContent=`${method},用时：${time/1000}s,去重后长度为：${len}`;
        document.body.appendChild(p);
    }

    //方法1：嵌套循环
    function fun1(arr,prop){
        const start=performance.now();
        const res=[];
        for (let i = 0; i < arr.length; i++) {
            let flag=false;
            for (let j = 0; j < res.length; j++) {
                if(res[j][prop]===arr[i][prop]){
                    flag=true;
                    break;
                }
            }
            if(!flag){
                res.push(arr[i]);
            }
        }
        const end=performance.now();
        showPrint(`方法1：嵌套循环【时间复杂度O(n^2)】`,end-start,res.length);
        return res;
    }

    //方法2：Set
    function fun2(arr,prop){
        const start=performance.now();
        const memory=new Set();
        const res=[];
        arr.forEach(item=>{
            const val=item[prop];
            if(!memory.has(val)){
                memory.add(val);
                res.push(item);
            }
        });
        const end=performance.now();
        showPrint(`方法2：Set【时间复杂度O(n)】`,end-start,res.length);
        return res;
    }

    //方法3：Map
    function fun3(arr,prop){
        const start=performance.now();
        const res=[];
        const memory=new Map();
        for (let i = 0; i < arr.length; i++) {
            const val=arr[i][prop];
            if(!memory.has(val)){
                memory.set(val,true);
                res.push(arr[i]);
            }
        }
        const end=performance.now();
        showPrint(`方法3：Map【时间复杂度O(n)】`,end-start,res.length);
        return res;
    }

    //方法4：先排序再去重
    function fun4(arr,prop) {
        const start=performance.now();
        const sorted=[...arr].sort((a,b)=>a[prop]-b[prop]);
        const res=[];
        let lastVal;
        sorted.forEach(item=>{
            const val=item[prop];
            if (val!==lastVal){
                lastVal=val;
                res.push(item);
            }
        });
        const end=performance.now();
        showPrint(`方法4：先排序再去重`,end-start,res.length);
        return res;
    }

    //方法5：普通对象作为哈希表（利用JS对象的“键名唯一”的特性）
    function fun5(arr, prop) {
        const start=performance.now();
        const res=[];
        const memory={};
        for (let i = 0; i < arr.length; i++) {
            const val=arr[i][prop];
            if (!memory.hasOwnProperty(val)){
                memory[val]=true;
                res.push(arr[i]);
            }
        }
        const end=performance.now();
        showPrint(`方法5：普通对象作为哈希表【时间复杂度O(n)】`,end-start,res.length);
        return res;
    }
    //运行测试
    fun1(objs,prop);
    fun2(objs,prop);
    fun3(objs,prop);
    fun4(objs,prop);
    fun5(objs,prop);
</script>
<script>

</script>
</body>
</html>